package practise.alogrithm.hundredInterviewQuestions.secondTime;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Created by Richard on 7/26/2014.
 */
public class TreeNodeIterator implements Iterable<TreeNode> {
    private TreeNode treeNode;

    public TreeNodeIterator(TreeNode treeNode) {
        this.treeNode = treeNode;
    }

    @Override
    public Iterator<TreeNode> iterator() {
        return new TreeNodeIterate(treeNode);
    }

    public static void main(String[] args){
        TreeNode treeNode1 = TreeBuilder.createTreeByArrayInWidth(new int[]{1,2,3,4,5,6,7});
        TreeNodeIterator iterator = new TreeNodeIterator(treeNode1);
        for(TreeNode treeNode2 : iterator){
            System.out.print("node:"+treeNode2.getValue());
        }
    }
}

class TreeNodeIterate implements Iterator<TreeNode>{
    private int lengthOfLevel;
    private int indexOfLevel;
    private int level =0;
    private List<TreeNode> queue;
    public TreeNodeIterate(TreeNode node){
        queue = new ArrayList<>();
        queue.add(node);
        lengthOfLevel = queue.size();
        indexOfLevel=lengthOfLevel;
        level=1;
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    @Override
    public TreeNode next() {
        TreeNode temp = queue.remove(0);
        if(temp.getLeft()!=null){
            queue.add(temp.getLeft());
        }
        if(temp.getRight()!=null){
            queue.add(temp.getRight());
        }
        if(indexOfLevel==lengthOfLevel){
            indexOfLevel=1;
            level++;
            lengthOfLevel = queue.size();
        }
        else{
            indexOfLevel++;
        }
        return temp;
    }
}
